前言

上一篇介紹函數式程式設計(Functional Programming)的概念，這次再進一步應用它及抽象語法樹(Abstract Syntax Tree, AST)開發一個簡單的直譯器(Interpreter)。

抽象語法樹(Abstract Syntax Tree, AST)

抽象語法樹(AST)可幫我們解析程式語法，轉換成一個具有執行順序的樹(Tree)，接著就進行程式評估，得到執行結果。Python內建AST模組，不需額外安裝，直接可以使用。

範例1. 顯示AST解析的樹狀結構，檔案名稱是ast1.py。

import ast
import pprint

code = 'a + b - 5'
tree = ast.parse(code)
pprint.pprint(ast.dump(tree))

執行結果：

("Module(body=[Expr(value=BinOp(left=Name(id='a', ctx=Load()), op=Add(), "
 "right=Name(id='b', ctx=Load())))], type_ignores=[])")

樹的左邊(left)節點是a，右邊(left)節點是b，運算符號是Add。

程式更複雜一些，加入判斷式，code改為：

code = 'if x > 5: a + b - 5'

完整程式如下：

import ast
import pprint

code = 'if x > 5: a + b - 5'
tree = ast.parse(code)
pprint.pprint(ast.dump(tree))

執行結果：

("Module(body=[If(test=Compare(left=Name(id='x', ctx=Load()), ops=[Gt()], "
 'comparators=[Constant(value=5)]), '
 "body=[Expr(value=BinOp(left=BinOp(left=Name(id='a', ctx=Load()), op=Add(), "
 "right=Name(id='b', ctx=Load())), op=Sub(), right=Constant(value=5)))], "
 'orelse=[])], type_ignores=[])')

可以看到解析也沒有問題。

範例2. 顯示AST解析的樹狀結構圖，檔案名稱是ast2.py。需先安裝GraphViz軟體，參閱GraphViz文件說明，注意，安裝後須將bin路徑加到環境變數path中，並安裝graphviz、dotplus套件。

pip install graphviz dotplus

程式碼：

import ast
import pprint
from graphviz import Digraph

# 使用 dot 語言描述圖形，使用GraphViz將dot轉為圖檔
def draw_ast(tree):
    def add_node(node, parent=None):
        node_name = str(node.__class__.__name__)
        dot.node(str(id(node)), node_name)
        if parent:
            dot.edge(str(id(parent)), str(id(node)))
        for child in ast.iter_child_nodes(node):
            add_node(child, node)
            
    dot = Digraph()
    add_node(tree)
    dot.format = 'png'
    dot.render('my_ast', view=True)

# AST 解析
code = 'a + b - 5'
tree = ast.parse(code)
pprint.pprint(ast.dump(tree))

# 繪製 AST
draw_ast(tree)

執行結果：產生dot檔案my_ast及my_ast.png。

抽象語法樹 + Functional Programming

要如何應用AST樹的資訊進行程式評估，得到執行結果，就必須應用上一篇Functional Programming的作法，筆者參閱How I made a Math Evaluator on 24 lines of Python code一文，直接自它的GitHub複製MathEvaluator/src/math_evaluator
/explicit.py，另存成math_evaluator.py。

範例3. 呼叫math_evaluator.py，檔案名稱為ast3.py。

from math_evaluator import calc

code = '10 + 2 - 5'
print(calc(code))

1. math_evaluator.py主要使用遞迴解析樹狀結構，程式碼較長，不在此說明，請參閱筆者的GitHub。
2. 執行結果無誤：10 + 2 - 5 = 7。注意，math_evaluator.py中使用match指令，需使用Python v3.10或以上版本。

範例4. 程式碼使用變數，例如【a + b -5】，檔案名稱為ast4.py。

1. 執行錯誤，會出現【a + b -5】未知(unknown)，須將math_evaluator.py第38行改為：

case x:
    try:
        value = eval(x.id) # 評估變數，例如a、b
        return value

2. 將修改後的math_evaluator.py內容複製到主程式中，因為變數宣告必須讓評估程式(math_evaluator.py)能夠存取。

3. 測試：

a = 10
b = 2
code = 'a + b - 5'
tree = ast.parse(code, mode="eval").body
print(compute(tree))

4. 執行結果無誤：a + b - 5 = 7。

範例4. 將math_evaluator.py改寫為類別，與主程式分離，檔案名稱為ast5.py、evaluator_lib.py。

1. evaluator_lib.py內含evaluator類別，初始化(init)接收命名變數(**arg)參數，以便將變數傳入。

    def __init__(self, **arg):
        self.arg = arg

2. 變數評估改為：

case x:
    value = self.arg[x.id] # 以字典取變數值
    return value

3. 測試：

from evaluator_lib import evaluator

code = 'a + b - 5'
obj = evaluator(a=10, b=2)
print(obj.calc(code))

4. 執行結果無誤：a + b - 5 = 7。

其實Python已有提供以上的評估程式，就是eval指令，測試如下：

a = 10
b = 2
code = 'a + b - 5'
eval(code)

答案與上述程式相同，那我們為什麼要費力撰寫相關程式呢? 自行開發的評估器有以下擴充性：

1. 可以增加更多自訂的運算符號。
2. 可以改變運算符號的預設功能，例如將【+】改為可以跳過例假日的營業日期運算，2024/9/20 + 1 = 2024/9/23，因為2024/9/21、2024/9/22放假。
3. 可以撰寫解析多行的直譯器，請參見下面說明。

多行程式解析

若要實作一個完整的直譯器，解析多行程式，可參考Asteval套件作法。

1. 安裝Asteval套件：pip install asteval。
2. 測試：python asteval_test.py。

from asteval import Interpreter

aeval = Interpreter()

# 定義一個函數
code = """def func(a, b):
    return a + b - 5
"""
aeval(code)

# 測試
print(aeval("func(10, 2)"))

3. 執行結果無誤：a + b - 5 = 7。

Asteval原始碼近1600行，有待後續努力研究。

結語

透過以上的實作後，我們就有能力撰寫一個特定領域的語言(Domain-Specific Language, DSL)，例如自訂交易策略，簡單範例如下：

# 如果 當日收盤價 > 前日收盤價，則買進股票，否則保持部位不動
if close0 > close1: sell else hold

筆者職涯中曾開發多個類似的系統，例如電信業的開通系統(Provisioning system)，它必須介接許多交換機，每一個交換機有不同的通訊協定、交換資料的格式及API，隨著公司業務的擴展須不斷增加服務，如何確保既有服務的穩定運行，又要增加新功能，如果當時能使用Functional Programming系統應該可以發展的更好。Functional Programming也可以實作工廠模式(Factory Pattern)，可參閱筆者的部落文【工廠方法設計模式(Python)】。

本系列的程式碼會統一放在GitHub，本篇的程式放在src/5資料夾，歡迎讀者下載測試，如有錯誤或疏漏，請不吝指正。